{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sort Transformed Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #two-pointers #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #双指针 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sortTransformedArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有序转化数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个已经<strong>&nbsp;排好序</strong>&nbsp;的整数数组&nbsp;<code>nums</code>&nbsp;和整数&nbsp;<code>a</code>&nbsp;、&nbsp;<code>b</code>&nbsp;、&nbsp;<code>c</code>&nbsp;。对于数组中的每一个元素&nbsp;<code>nums[i]</code>&nbsp;，计算函数值&nbsp;<code>f(<em>x</em>) = <em>ax</em><sup>2</sup> + <em>bx</em> + c</code>&nbsp;，请 <em>按升序返回数组</em> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>nums = [-4,-2,2,4], a = 1, b = 3, c = 5\n",
    "<strong>输出: </strong>[3,9,15,33]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>nums = [-4,-2,2,4], a = -1, b = 3, c = 5\n",
    "<strong>输出: </strong>[-23,-5,1,7]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 200</code></li>\n",
    "\t<li><code>-100 &lt;= nums[i], a, b, c &lt;= 100</code></li>\n",
    "\t<li><code>nums</code>&nbsp;按照 <strong>升序排列</strong></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你可以在时间复杂度为&nbsp;<code>O(n)</code>&nbsp;的情况下解决这个问题吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sort-transformed-array](https://leetcode.cn/problems/sort-transformed-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sort-transformed-array](https://leetcode.cn/problems/sort-transformed-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-4,-2,2,4]\\n1\\n3\\n5', '[-4,-2,2,4]\\n-1\\n3\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: [int], a: int, b: int, c: int) -> [int]:\n",
    "        for i, num in enumerate(nums):\n",
    "            nums[i] = a * (num ** 2) + b * num + c\n",
    "        nums = sorted(nums)\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = nums[i] ** 2 * a + nums[i] * b + c\n",
    "        nums.sort()\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if a == 0:\n",
    "            if b > 0:\n",
    "                return [b * num + c for num in nums]\n",
    "            elif b == 0:\n",
    "                return [c] * n\n",
    "            else:\n",
    "                return [b * num + c for num in nums][::-1]\n",
    "\n",
    "        mid = -b / 2 / a\n",
    "        left = []\n",
    "        right = []\n",
    "        for num in nums:\n",
    "            if num <= mid:\n",
    "                left.append(a * num**2 + b * num + c)\n",
    "            else:\n",
    "                right.append(a * num**2 + b * num + c)\n",
    "        if a > 0:\n",
    "            left.reverse()\n",
    "        else:\n",
    "            right.reverse()\n",
    "\n",
    "        i = 0\n",
    "        j = 0\n",
    "        ans = []\n",
    "        while i < len(left) and j < len(right):\n",
    "            if left[i] <= right[j]:\n",
    "                ans.append(left[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                ans.append(right[j])\n",
    "                j += 1\n",
    "        ans += left[i:]\n",
    "        ans += right[j:]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        nums = [a*x*x + b*x + c for x in nums]\n",
    "        # if a == 0:\n",
    "        #     if b >= 0:\n",
    "        #         return nums\n",
    "        #     return nums[::-1]\n",
    "        # if a < 0:\n",
    "        #     ans = []\n",
    "        #     l,r = 0,len(nums) - 1\n",
    "        #     while l <= r:\n",
    "        #         if nums[l] <= nums[r]:\n",
    "        #             ans.append(nums[l])\n",
    "        #             l += 1\n",
    "        #         else:\n",
    "        #             ans.append(nums[r])\n",
    "        #             r -= 1\n",
    "        #     return ans\n",
    "        # else:\n",
    "        #     ans = []\n",
    "        #     l,r =0,len(nums) - 1\n",
    "        #     while l <= r:\n",
    "        #         if nums[l] >= nums[r]:\n",
    "        #             ans.append(nums[l])\n",
    "        #             l += 1\n",
    "        #         else:\n",
    "        #             ans.append(nums[r])\n",
    "        #             r -= 1\n",
    "        #     return ans[::-1]\n",
    "        return sorted(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        res = []\n",
    "        def quadraticFunction (x):\n",
    "            return a * (x) ** 2 + b * x + c\n",
    "        def findInsertIdx(target):\n",
    "            left, right = 0, len(res) - 1\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if res[mid] == target:\n",
    "                    return mid\n",
    "                elif res[mid] > target:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return left\n",
    "\n",
    "        for num in nums:\n",
    "            res_num = quadraticFunction(num)\n",
    "            idx = findInsertIdx(res_num)\n",
    "            res[idx:idx] = [res_num]\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = self.f(nums[i],a,b,c)\n",
    "            \n",
    "        return sorted(nums)\n",
    "    \n",
    "    \n",
    "    def f(self, x, a, b, c):\n",
    "       \n",
    "         return a * x**2 + b * x + c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = self.f(nums[i],a,b,c)\n",
    "            \n",
    "        return sorted(nums)\n",
    "    \n",
    "    \n",
    "    def f(self, x, a, b, c):\n",
    "       \n",
    "         return a * x**2 + b * x + c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        ans = []\n",
    "        for i in nums:\n",
    "            num = a*i**2 + b*i + c\n",
    "            ans.append(num)\n",
    "        return sorted(ans)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        def func(x):\n",
    "            return a*(x**2) + b*x + c\n",
    "\n",
    "        def left_to_right(nums):\n",
    "            return list(map(lambda x:func(x), nums))\n",
    "        \n",
    "        def right_to_left(nums):\n",
    "            return list(map(lambda x:func(x), nums[::-1]))\n",
    "        \n",
    "        def double_pointers(nums):\n",
    "            size = len(nums)\n",
    "            i, j, k = 0, size -1, size -1\n",
    "            if a > 0:\n",
    "                res = [0 for _ in range(size)]\n",
    "                while i <= j:\n",
    "                    di = func(nums[i])\n",
    "                    dj = func(nums[j])\n",
    "                    if di >= dj:\n",
    "                        res[k] = di\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        res[k] = dj\n",
    "                        j -= 1\n",
    "                    k -= 1\n",
    "            else:\n",
    "                res = []\n",
    "                while i <= j:\n",
    "                    di = func(nums[i])\n",
    "                    dj = func(nums[j])\n",
    "                    if di <= dj:\n",
    "                        res.append(di)\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        res.append(dj)\n",
    "                        j -= 1\n",
    "            return res\n",
    "        \n",
    "        if a == 0:\n",
    "            return left_to_right(nums) if b > 0 else right_to_left(nums)\n",
    "        \n",
    "        elif a > 0:\n",
    "            mid = (-b)/(2*a)\n",
    "            if nums[-1] <= mid:\n",
    "                return right_to_left(nums)\n",
    "            elif nums[0] >= mid:\n",
    "                return left_to_right(nums)\n",
    "            else:\n",
    "                return double_pointers(nums)\n",
    "        else:\n",
    "            mid = (-b)/(2*a)\n",
    "            if nums[-1] <= mid:\n",
    "                return left_to_right(nums)\n",
    "            elif nums[0] >= mid:\n",
    "                return right_to_left(nums)\n",
    "            else:\n",
    "                return double_pointers(nums)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        # Quadratic function\n",
    "        quad = lambda x: a*x*x + b*x + c\n",
    "\n",
    "        # If a = 0 and b = 0, the transformation is a constant\n",
    "        if a == 0 and b == 0:\n",
    "            return [c] * len(nums)\n",
    "\n",
    "        # If a = 0, sort based on b\n",
    "        if a == 0:\n",
    "            return [quad(x) for x in sorted(nums, reverse=(b < 0))]\n",
    "\n",
    "        # Calculate the mid value\n",
    "        mid = -b / (2*a)\n",
    "\n",
    "        # Calculate distance from mid\n",
    "        newNums = [abs(num - mid) for num in nums]\n",
    "\n",
    "        left, right = 0, len(nums) - 1\n",
    "        result = deque()\n",
    "\n",
    "        while left <= right:\n",
    "            if a > 0:\n",
    "                if newNums[left] < newNums[right]:\n",
    "                    result.appendleft(quad(nums[right]))\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    result.appendleft(quad(nums[left]))\n",
    "                    left += 1\n",
    "            else:\n",
    "                if newNums[left] < newNums[right]:\n",
    "                    result.append(quad(nums[right]))\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    result.append(quad(nums[left]))\n",
    "                    left += 1\n",
    "\n",
    "        return list(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if a == 0:\n",
    "            res = [a * x * x + b * x + c for x in nums]\n",
    "            return res if b >= 0 else res[::-1]\n",
    "        mid = -b / (2 * a)\n",
    "        r = bisect_left(nums, mid)\n",
    "        l = r - 1\n",
    "        res = []\n",
    "        for _ in range(n):\n",
    "            if self.check(nums, l, r, mid):\n",
    "                x = nums[l]\n",
    "                l -= 1\n",
    "            else:\n",
    "                x = nums[r]\n",
    "                r += 1\n",
    "            res.append(a * x * x + b * x + c)\n",
    "        return res if a > 0 else res[::-1]\n",
    "\n",
    "    # return True if nums[l] is closer to mid than nums[r]\n",
    "    def check(self, nums, l, r, mid):\n",
    "        if l < 0: return False\n",
    "        if r > len(nums) - 1: return True\n",
    "        return abs(mid - nums[l]) <= abs(mid - nums[r])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if a == 0:\n",
    "            res = [a * x * x + b * x + c for x in nums]\n",
    "            return res if b >= 0 else res[::-1]\n",
    "        mid = -b / (2 * a)\n",
    "        r = bisect_left(nums, mid)\n",
    "        l = r - 1\n",
    "        res = []\n",
    "        for _ in range(n):\n",
    "            if self.check(nums, l, r, mid):\n",
    "                x = nums[l]\n",
    "                l -= 1\n",
    "            else:\n",
    "                x = nums[r]\n",
    "                r += 1\n",
    "            res.append(a * x * x + b * x + c)\n",
    "        return res if a > 0 else res[::-1]\n",
    "\n",
    "    # return True if nums[l] is closer to mid than nums[r]\n",
    "    def check(self, nums, l, r, mid):\n",
    "        if l < 0: return False\n",
    "        if r > len(nums) - 1: return True\n",
    "        return abs(mid - nums[l]) <= abs(mid - nums[r])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 注意：python 代码由 chatGPT\\U0001f916 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。\n",
    "# 本代码已经通过力扣的测试用例，应该可直接成功提交。\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        # 双指针，相向而行，逼近对称轴\n",
    "        i, j = 0, len(nums) - 1\n",
    "        # 如果开口朝上，越靠近对称轴函数值越小\n",
    "        # 如果开口朝下，越靠近对称轴函数值越大\n",
    "        p = len(nums) - 1 if a > 0 else 0\n",
    "        res = [0 for _ in range(len(nums))]\n",
    "        # 执行合并两个有序数组的逻辑\n",
    "        while i <= j:\n",
    "            v1 = self.f(nums[i], a, b, c)\n",
    "            v2 = self.f(nums[j], a, b, c)\n",
    "            if a > 0:\n",
    "                # 如果开口朝上，越靠近对称轴函数值越小\n",
    "                if v1 > v2:\n",
    "                    res[p] = v1\n",
    "                    p -= 1\n",
    "                    i += 1\n",
    "                else:\n",
    "                    res[p] = v2\n",
    "                    p -= 1\n",
    "                    j -= 1\n",
    "            else:\n",
    "                # 如果开口朝下，越靠近对称轴函数值越大\n",
    "                if v1 > v2:\n",
    "                    res[p] = v2\n",
    "                    p += 1\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    res[p] = v1\n",
    "                    p += 1\n",
    "                    i += 1\n",
    "        return res\n",
    "\n",
    "    def f(self, x: int, a: int, b: int, c: int) -> int:\n",
    "        return a*x*x + b*x + c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        if a==0:\n",
    "            for i in range(len(nums)):\n",
    "                nums[i]=b*nums[i]+c\n",
    "            if b>=0:\n",
    "                return nums\n",
    "            else:\n",
    "                return nums[::-1]\n",
    "        \n",
    "        mid=-b/(2*a)\n",
    "        mid_index='z'\n",
    "        mid_min=99999999\n",
    "        for i in range(len(nums)):\n",
    "            nums[i]=abs(nums[i]-mid)\n",
    "            if nums[i]<mid_min:\n",
    "                mid_min=nums[i]\n",
    "                mid_index=i\n",
    "\n",
    "        left,right=mid_index,mid_index+1\n",
    "        ret=[]\n",
    "        for i in range(len(nums)):\n",
    "            if left<0 or right>=len(nums):\n",
    "                break\n",
    "            if nums[left]<nums[right]:\n",
    "                ret.append(nums[left])\n",
    "                left-=1\n",
    "            else:\n",
    "                ret.append(nums[right])\n",
    "                right+=1\n",
    "            if left<0 or right>=len(nums):\n",
    "                break\n",
    "        while left>-1:\n",
    "            ret.append(nums[left])\n",
    "            left-=1\n",
    "        while right<len(nums):\n",
    "            ret.append(nums[right])\n",
    "            right+=1\n",
    "        if a<0:\n",
    "            ret=ret[::-1]\n",
    "        def change_to_int(num):\n",
    "            if num-math.floor(num)>0.5:\n",
    "                return math.floor(num)+1\n",
    "            else:\n",
    "                return math.floor(num)\n",
    "\n",
    "        bias=c-b*b/(4*a)\n",
    "        for i in range(len(nums)):\n",
    "            ret[i]=change_to_int(ret[i]*ret[i]*a+bias)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        ans = []\n",
    "        for i in nums:\n",
    "            ans.append(a * i ** 2 + b * i + c)\n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # Bisect + two pointers. Time O(n) Space O(1)\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        # handle the case where a == 0, even b == 0\n",
    "        if a == 0:\n",
    "            res = [a * x * x + b * x + c for x in nums]\n",
    "            return res if b >= 0 else res[::-1]\n",
    "        mid = -b / (2 * a)\n",
    "        r = bisect_left(nums, mid)\n",
    "        l = r - 1\n",
    "        res = []\n",
    "        for _ in range(n):\n",
    "            if self.check(nums, l, r, mid):\n",
    "                x = nums[l]\n",
    "                l -= 1\n",
    "            else:\n",
    "                x = nums[r]\n",
    "                r += 1\n",
    "            res.append(a * x * x + b * x + c)\n",
    "        return res if a > 0 else res[::-1]\n",
    "\n",
    "    # return True if nums[l] is closer to mid than nums[r]\n",
    "    def check(self, nums, l, r, mid):\n",
    "        if l < 0: return False\n",
    "        if r > len(nums) - 1: return True\n",
    "        return abs(mid - nums[l]) <= abs(mid - nums[r])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        if a == 0:\n",
    "            return sorted([b * num + c for num in nums])\n",
    "        else:\n",
    "            x = -b/(2 * a)\n",
    "            arr1 = [a * num * num + b * num + c for num in nums if num < x]\n",
    "            arr2 = [a * num * num + b * num + c for num in nums if num >= x]\n",
    "            if a < 0:\n",
    "                arr1 = arr1[::-1]\n",
    "                arr2 = arr2[::-1]\n",
    "            i, j = len(arr1) - 1, 0\n",
    "            res = []\n",
    "            # print(arr1, arr2)\n",
    "            while i >= 0 and j < len(arr2):\n",
    "                if arr1[i] < arr2[j]:\n",
    "                    res.append(arr1[i])\n",
    "                    i -= 1\n",
    "                else:\n",
    "                    res.append(arr2[j])\n",
    "                    j += 1\n",
    "            if i >= 0:\n",
    "                res += arr1[:i+1][::-1]\n",
    "            else:\n",
    "                res += arr2[j:]\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if a == 0:\n",
    "            if b > 0:\n",
    "                return [b * num + c for num in nums]\n",
    "            elif b == 0:\n",
    "                return [c] * n\n",
    "            else:\n",
    "                return [b * num + c for num in nums][::-1]\n",
    "\n",
    "        mid = -b / 2 / a\n",
    "        left = []\n",
    "        right = []\n",
    "        for num in nums:\n",
    "            if num <= mid:\n",
    "                left.append(a * num**2 + b * num + c)\n",
    "            else:\n",
    "                right.append(a * num**2 + b * num + c)\n",
    "        if a > 0:\n",
    "            left.reverse()\n",
    "        else:\n",
    "            right.reverse()\n",
    "\n",
    "        i = 0\n",
    "        j = 0\n",
    "        ans = []\n",
    "        while i < len(left) and j < len(right):\n",
    "            if left[i] <= right[j]:\n",
    "                ans.append(left[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                ans.append(right[j])\n",
    "                j += 1\n",
    "        ans += left[i:]\n",
    "        ans += right[j:]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        # axis=-b/(2*a)\n",
    "        result=[]\n",
    "        for i in range(len(nums)):\n",
    "            x=nums[i]\n",
    "            result.append(a*x*x+b*x+c)\n",
    "        return sorted(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        def cal(num):\n",
    "            return a*num*num+b*num+c\n",
    "        res = []\n",
    "        start = 0\n",
    "        end = len(nums)-1\n",
    "        while start <= end:\n",
    "            start_cal = cal(nums[start])\n",
    "            end_cal = cal(nums[end])\n",
    "            if a>=0:\n",
    "                if start_cal >= end_cal:\n",
    "                    res.append(start_cal)\n",
    "                    start +=1\n",
    "                else:\n",
    "                    res.append(end_cal)\n",
    "                    end -=1\n",
    "            else:\n",
    "                if start_cal <= end_cal:\n",
    "                    res.append(start_cal)\n",
    "                    start +=1\n",
    "                else:\n",
    "                    res.append(end_cal)\n",
    "                    end -=1\n",
    "        if a>=0:\n",
    "            res.reverse()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        ans=[]\n",
    "        for n in nums:\n",
    "            ans.append(a*n*n+b*n+c)\n",
    "        ans.sort()\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if a == 0:\n",
    "            if b > 0:\n",
    "                return [b * num + c for num in nums]\n",
    "            elif b == 0:\n",
    "                return [c] * n\n",
    "            else:\n",
    "                return [b * num + c for num in nums][::-1]\n",
    "\n",
    "        mid = -b / 2 / a\n",
    "        left = []\n",
    "        right = []\n",
    "        for num in nums:\n",
    "            if num <= mid:\n",
    "                left.append(a * num**2 + b * num + c)\n",
    "            else:\n",
    "                right.append(a * num**2 + b * num + c)\n",
    "        if a > 0:\n",
    "            left.reverse()\n",
    "        else:\n",
    "            right.reverse()\n",
    "\n",
    "        i = 0\n",
    "        j = 0\n",
    "        ans = []\n",
    "        while i < len(left) and j < len(right):\n",
    "            if left[i] <= right[j]:\n",
    "                ans.append(left[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                ans.append(right[j])\n",
    "                j += 1\n",
    "        ans += left[i:]\n",
    "        ans += right[j:]\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        if a==0:\n",
    "            for i in range(len(nums)):\n",
    "                nums[i]=b*nums[i]+c\n",
    "            if b>=0:\n",
    "                return nums\n",
    "            else:\n",
    "                return nums[::-1]\n",
    "        \n",
    "        mid=-b/(2*a)\n",
    "        mid_index='z'\n",
    "        mid_min=99999999\n",
    "        for i in range(len(nums)):\n",
    "            nums[i]=abs(nums[i]-mid)\n",
    "            if nums[i]<mid_min:\n",
    "                mid_min=nums[i]\n",
    "                mid_index=i\n",
    "\n",
    "        left,right=mid_index,mid_index+1\n",
    "        ret=[]\n",
    "        for i in range(len(nums)):\n",
    "            if left<0 or right>=len(nums):\n",
    "                break\n",
    "            if nums[left]<nums[right]:\n",
    "                ret.append(nums[left])\n",
    "                left-=1\n",
    "            else:\n",
    "                ret.append(nums[right])\n",
    "                right+=1\n",
    "            if left<0 or right>=len(nums):\n",
    "                break\n",
    "        while left>-1:\n",
    "            ret.append(nums[left])\n",
    "            left-=1\n",
    "        while right<len(nums):\n",
    "            ret.append(nums[right])\n",
    "            right+=1\n",
    "        if a<0:\n",
    "            ret=ret[::-1]\n",
    "        def change_to_int(num):\n",
    "            if num-math.floor(num)>0.5:\n",
    "                return math.floor(num)+1\n",
    "            else:\n",
    "                return math.floor(num)\n",
    "\n",
    "        bias=c-b*b/(4*a)\n",
    "        for i in range(len(nums)):\n",
    "            ret[i]=change_to_int(ret[i]*ret[i]*a+bias)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        if not a:\n",
    "            return [b * x + c for x in nums][::(-1)**(b < 0)]\n",
    "        result, left, m = [], [], -b / a / 2\n",
    "        f = lambda x: x * (a * x + b) + c\n",
    "        for x in nums:\n",
    "            if x < m:\n",
    "                left.append(x)\n",
    "            else:\n",
    "                while left and m - left[-1] <= x - m:\n",
    "                    result.append(f(left.pop()))\n",
    "                result.append(f(x))\n",
    "        while left:\n",
    "            result.append(f(left.pop()))\n",
    "        return result[::(-1)**(a<0)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        if a == 0:\n",
    "            if b >= 0:\n",
    "                return [b*val + c for val in nums]\n",
    "            else:\n",
    "                return [b*val + c for val in nums][::-1]\n",
    "\n",
    "        n = len(nums)\n",
    "        left, right = 0, n-1\n",
    "        ret = [0] * n\n",
    "        mid_val = -b / (2*a)\n",
    "        \n",
    "        def get_val(val):\n",
    "            return a*(val**2) + b*val + c\n",
    "\n",
    "        if a > 0:\n",
    "            idx = n-1\n",
    "            while left <= right:\n",
    "                left_val, right_val = nums[left], nums[right]\n",
    "                if abs(mid_val - left_val) <= abs(right_val - mid_val):\n",
    "                    ret[idx] = get_val(right_val)\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    ret[idx] = get_val(left_val)\n",
    "                    left += 1\n",
    "                idx -= 1\n",
    "\n",
    "        elif a < 0:\n",
    "            idx = 0\n",
    "            while left <= right:\n",
    "                left_val, right_val = nums[left], nums[right]\n",
    "                if abs(mid_val - left_val) <= abs(right_val - mid_val):\n",
    "                    ret[idx] = get_val(right_val)\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    ret[idx] = get_val(left_val)\n",
    "                    left += 1\n",
    "                idx += 1\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "      # 暴力解决\n",
    "      # ans = list()\n",
    "      # for x in nums:\n",
    "      #   ans.append(a*x*x + b*x + c)\n",
    "      # ans.sort()\n",
    "      # return ans\n",
    "\n",
    "\n",
    "      # 双指针\n",
    "      # 如果a>0 是向上的抛物线，如果a<0 是向下的抛物线\n",
    "      def f(x):\n",
    "        return a*x*x + b*x + c\n",
    "      \n",
    "      n = len(nums)\n",
    "      ans = [0]*n\n",
    "      i, j = 0, n-1\n",
    "\n",
    "      idx = n-1 if a>0 else 0\n",
    "      while i <= j:\n",
    "        if a > 0:\n",
    "          if f(nums[i]) >= f(nums[j]):\n",
    "            ans[idx] = f(nums[i])\n",
    "            i+=1\n",
    "          else:\n",
    "            ans[idx] = f(nums[j])\n",
    "            j-=1\n",
    "          idx-=1\n",
    "        else:\n",
    "          if f(nums[i]) >= f(nums[j]):\n",
    "            ans[idx] = f(nums[j])\n",
    "            j-=1\n",
    "          else:\n",
    "            ans[idx] = f(nums[i])\n",
    "            i+=1\n",
    "          idx+=1\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        # Quadratic function\n",
    "        quad = lambda x: a*x*x + b*x + c\n",
    "\n",
    "        # If a = 0 and b = 0, the transformation is a constant\n",
    "        if a == 0 and b == 0:\n",
    "            return [c] * len(nums)\n",
    "\n",
    "        # If a = 0, process based on b\n",
    "        if a == 0:\n",
    "            if b > 0:\n",
    "                return [quad(x) for x in nums]\n",
    "            else:\n",
    "                return [quad(x) for x in reversed(nums)]\n",
    "\n",
    "        # Calculate the mid value\n",
    "        mid = -b / (2*a)\n",
    "\n",
    "        # Calculate distance from mid\n",
    "        newNums = [abs(num - mid) for num in nums]\n",
    "\n",
    "        left, right = 0, len(nums) - 1\n",
    "        result = deque()\n",
    "\n",
    "        while left <= right:\n",
    "            if a > 0:\n",
    "                if newNums[left] < newNums[right]:\n",
    "                    result.appendleft(quad(nums[right]))\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    result.appendleft(quad(nums[left]))\n",
    "                    left += 1\n",
    "            else:\n",
    "                if newNums[left] < newNums[right]:\n",
    "                    result.append(quad(nums[right]))\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    result.append(quad(nums[left]))\n",
    "                    left += 1\n",
    "\n",
    "        return list(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "      # 暴力解决\n",
    "      ans = list()\n",
    "      for x in nums:\n",
    "        ans.append(a*x*x + b*x + c)\n",
    "      ans.sort()\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        def cal(x, a, b, c):\n",
    "            return a * x * x + b * x + c\n",
    "\n",
    "        if len(nums) == 0:\n",
    "            return []\n",
    "\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "\n",
    "        # a > 0 / a < 0\n",
    "        new_nums = [0] * len(nums)\n",
    "        if a > 0:\n",
    "            i = len(nums) - 1\n",
    "            while left <= right:\n",
    "                l = cal(nums[left], a, b, c)\n",
    "                r = cal(nums[right], a, b, c)\n",
    "                if l < r:\n",
    "                    new_nums[i] = r\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    new_nums[i] = l\n",
    "                    left += 1\n",
    "                i -= 1\n",
    "        else:\n",
    "            i = 0\n",
    "            while left <= right:\n",
    "                l = cal(nums[left], a, b, c)\n",
    "                r = cal(nums[right], a, b, c)\n",
    "                if l < r:\n",
    "                    new_nums[i] = l\n",
    "                    left += 1\n",
    "                else:\n",
    "                    new_nums[i] = r\n",
    "                    right -= 1\n",
    "                i += 1\n",
    "        return new_nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        res = []\n",
    "        if a == 0:\n",
    "            for i in range(len(nums)):\n",
    "                res.append(b * nums[i] + c)\n",
    "            if b >= 0:\n",
    "                return res\n",
    "            else:\n",
    "                return res[::-1]\n",
    "        else:\n",
    "            x = -b / (2 * a)\n",
    "            left, right = 0, len(nums) - 1\n",
    "            while left <= right:\n",
    "                if abs(nums[left] - x) >= abs(nums[right] - x):\n",
    "                    res.append(a * nums[left]**2 + b * nums[left] + c)\n",
    "                    left += 1\n",
    "                else:\n",
    "                    res.append(a * nums[right]**2 + b * nums[right] + c)\n",
    "                    right -= 1\n",
    "                \n",
    "            if a > 0:\n",
    "                return res[::-1]\n",
    "            else:\n",
    "                return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        def quad(x):\n",
    "            return a*x*x + b*x + c\n",
    "        if a == 0:\n",
    "            ans = [b*x + c for x in nums]\n",
    "            return ans if b > 0 else ans[::-1]\n",
    "        n = len(nums)\n",
    "        l, r = 0, n - 1 \n",
    "        mn = -b/(2*a)\n",
    "        # print(f'mn={mn}')\n",
    "        ans = []\n",
    "        while l <= r:\n",
    "            if abs(nums[r] - mn) >= abs(mn - nums[l]):\n",
    "                # print(f'r={r},nums[r]={nums[r]}')\n",
    "                ans.append(quad(nums[r]))\n",
    "                r -= 1\n",
    "            else:\n",
    "                # print(f'l={l},nums[l]={nums[l]}')\n",
    "                ans.append(quad(nums[l]))\n",
    "                l += 1\n",
    "        # print(f'{ans}')\n",
    "        return ans[::-1] if a > 0 else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if a == 0:\n",
    "            if b == 0:\n",
    "                return [c] * n\n",
    "            if b > 0:\n",
    "                return [a * x ** 2 + b * x + c  for x in nums]\n",
    "            else:\n",
    "                return [a * nums[i] * nums[i] + b * nums[i] + c for i in range(n - 1, -1, -1)]\n",
    "        elif a > 0:\n",
    "            i, j = 0, n - 1\n",
    "            ret = [0] * n\n",
    "            index = n - 1\n",
    "            while i <= j:\n",
    "                if a * nums[i] * nums[i] + b * nums[i] + c >= a * nums[j] * nums[j] + b * nums[j] + c:\n",
    "                    ret[index] = a * nums[i] * nums[i] + b * nums[i] + c\n",
    "                    index -= 1\n",
    "                    i += 1\n",
    "                else:\n",
    "                    ret[index] = a * nums[j] * nums[j] + b * nums[j] + c\n",
    "                    index -= 1\n",
    "                    j -= 1\n",
    "            return ret\n",
    "        else:\n",
    "            i, j = 0, n - 1\n",
    "            index = 0\n",
    "            ret = [0] * n\n",
    "            while i <= j:\n",
    "                if a * nums[i] * nums[i] + b * nums[i] + c >= a * nums[j] * nums[j] + b * nums[j] + c:\n",
    "                    ret[index] = a * nums[j] * nums[j] + b * nums[j] + c\n",
    "                    index += 1\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    ret[index] = a * nums[i] * nums[i] + b * nums[i] + c\n",
    "                    index += 1\n",
    "                    i += 1\n",
    "            return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:\n",
    "        if not nums:\n",
    "            return nums\n",
    "        \n",
    "        res = [0] * len(nums)\n",
    "        p1 = 0\n",
    "        p2 = len(nums) - 1\n",
    "        # 从两边向中间走, a 来决定越走越大还是越走越小 --> 来决定从f(x) 是从大变小还是从小变大\n",
    "        # 对称轴具体是多少不重要\n",
    "        if a > 0 :\n",
    "            cur = len(nums) - 1\n",
    "        else:\n",
    "            cur =  0\n",
    "        \n",
    "        # 两边走向中间\n",
    "        while p1 <= p2:\n",
    "            v1 = self.func(a, b, c, nums[p1])\n",
    "            v2 = self.func(a, b, c, nums[p2])\n",
    "            # print(f'p1 = {p1} p2 = {p2} v1 = {v1} v2 = {v2} res[cur] = {res[cur]}')\n",
    "            if a > 0:\n",
    "                # 越往中间走越小, cur 从后向前添加\n",
    "                if v1 > v2:\n",
    "                    res[cur] =  v1\n",
    "                    p1 = p1 + 1\n",
    "                else:\n",
    "                    res[cur] = v2\n",
    "                    p2 = p2 - 1\n",
    "                \n",
    "                cur = cur - 1\n",
    "            else:\n",
    "                # 越往中间走越小, cur 从前向后添加\n",
    "                if v1 < v2:\n",
    "                    res[cur] = v1\n",
    "                    p1 = p1 + 1\n",
    "                else:\n",
    "                    res[cur] = v2\n",
    "                    p2 = p2 - 1\n",
    "\n",
    "                cur = cur + 1\n",
    "        \n",
    "        return res\n",
    "    \n",
    "    def func(self, a, b, c, x):\n",
    "        return a * x * x + b * x + c"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
